package com.atguigu.main.sort;

import java.util.Arrays;

/**
 * @author ：剧情再美终是戏
 * @description：堆排序
 * @mail : 13286520398@163.com
 * @date ：Created in 2020/3/1 9:48
 * @modified By：
 * @version: 1.0
 */
public class HeapSort {
    private static int heapsize;

    public static void main(String[] args) {
        int[] array = {0, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        heapsize = array.length;
        heapSort(array, heapsize);
        System.out.println(Arrays.toString(array));
    }

    private static void heapSort(int[] array, int length) {
        // 构建最大堆
        buildMaxHeap(array, length);

        for (int i = length - 1; i >= 1; i--) {
            // 将最大堆和最后一个元素交换位置
            swap(array, 0, i);
            // 当前数组未排序元素长度 -1
            heapsize -= 1;
            // 维护最大堆
            maxHeapify(array, 0);
        }
    }

    // 维护最大堆
    private static void maxHeapify(int[] array, int i) {
        // 当前下标的左节点  2 * i
        int l = 2 * i;
        // 当前节点的右节点 2 * i + 1
        int r = 2 * i + 1;

        // 在当前节点，左节点，右节点中，选择一个最大的节点
        int largest = i;
        if (l < heapsize && array[l] > array[i]) largest = l; // 这里需要先判断是否存在根节点
        if (r < heapsize && array[r] > array[largest]) largest = r;

        // 如果选择的最大的节点不等于当前节点
        if (largest != i) {
            // 最大节点和当前节点进行交换
            swap(array, i, largest);

            // 上面交换后之后，i 就已经是当前节点，左节点，右节点中最大的位置了
            // 那么交换之后，largest在其子叶中不一定是最大的，所以需要将维护 largest 以下的节点的最大堆问题
            // 递归将交换后的节点下面的节点维护最大堆
            maxHeapify(array, largest);
        }
    }

    // 构建最大堆
    private static void buildMaxHeap(int[] array, int length) {
        // 从最后的叶节点的根节点下标开始构建，循环到下标为 0 的时候就是完成了最大堆的构建了
        for (int i = length / 2; i >= 0; i--) {
            maxHeapify(array, i);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
